package cn.zifangsky.tree.binarytree.questions;

import org.junit.Test;

import cn.zifangsky.queue.LinkQueue;
import cn.zifangsky.tree.binarytree.BinaryTreeNode;

/**
 * LCA问题（Lowest Common Ancestor）：查找二叉树中两个节点的最近的公共祖先节点
 * XXX 继续思考流程？
 * @author zifangsky
 *
 */
public class Question18 {

	/**
	 * 查找二叉树中两个节点的最近的公共祖先节点
	 * 思路：
	 *     1. 从根节点开始分别左子树和右子树递归遍历，如果此时的root和targetNode1、targetNode2任意一个节点匹配，
	 * 则说明最近的公共祖先节点处于此时的root和根节点这条路径之上
	 * 	   2. 
	 * @时间复杂度 O(n)
	 * @param root 根节点
	 * @param targetNode1 目标节点1
	 * @param targetNode2 目标节点2
	 * @return
	 */
	public BinaryTreeNode<Integer> LCA(BinaryTreeNode<Integer> root,BinaryTreeNode<Integer> targetNode1,
			BinaryTreeNode<Integer> targetNode2){
		if(root == null){
			return null;
		}

		//为了避免无意义的子树判断，因此这个判断条件移到前面来判断
		if(root == targetNode1 || root == targetNode2){
			return root;
		}
		
		//
		BinaryTreeNode<Integer> leftLCA = LCA(root.getLeft(), targetNode1, targetNode2);
		BinaryTreeNode<Integer> rightLCA = LCA(root.getRight(), targetNode1, targetNode2);
		
		//左子树和右子树分别查找到一个目标节点，则说明此时的root是最近的公共祖先节点
		if(leftLCA != null && rightLCA != null){
			return root;
		}
		
		//公共祖先节点存在于此时的root和根节点这条路径之上
		if(leftLCA != null){
			return leftLCA;
		}else{
			return rightLCA;
		}
	}

	/**
	 * 测试用例
	 */
	@Test
	public void testMethods(){
		/**
		 * 使用队列构造一个供测试使用的二叉树
		 *     1
		 *   2    3
		 * 4  5  6  7
		 *   8 9  
		 */
		LinkQueue<BinaryTreeNode<Integer>> queue = new LinkQueue<BinaryTreeNode<Integer>>();
		BinaryTreeNode<Integer> root = new BinaryTreeNode<>(1); //根节点
		BinaryTreeNode<Integer> targetNode1 = null; //目标节点1
		BinaryTreeNode<Integer> targetNode2 = null; //目标节点2
		
		queue.push(root);
		BinaryTreeNode<Integer> temp = null;
		for(int i=2;i<10;i=i+2){
			BinaryTreeNode<Integer> tmpNode1 = new BinaryTreeNode<>(i);
			BinaryTreeNode<Integer> tmpNode2 = new BinaryTreeNode<>(i+1);
			
			temp = queue.pop();
			
			temp.setLeft(tmpNode1);
			temp.setRight(tmpNode2);
			
			if(i == 4){
				targetNode1 = tmpNode1;
				targetNode2 = tmpNode2;
			}else{
				queue.push(tmpNode1);
			}
			queue.push(tmpNode2);
		}

		//打印数字4和数字5最近的公共祖先节点
		BinaryTreeNode<Integer> result = LCA(root,targetNode1,targetNode2);
		System.out.println(result.getData());
	}

}
